package com.gitee.wsl.struct.tree.iterator

import com.gitee.wsl.struct.tree.NodeElement
import com.gitee.wsl.struct.tree.TreeElement

/**
 * Tree is iterated by using `Post-order Traversal Algorithm" In post-order traversal, we starting
 * from most left child. First visit all children of parent, then parent.
 *
 * ```
 * E.g.
 *                    1
 *                  / | \
 *                 /  |   \
 *               2    3     4
 *              / \       / | \
 *             5    6    7  8  9
 *            /   / | \
 *           10  11 12 13
 *
 * Output: 10 5 11 12 13 6 2 3 7 8 9 4 1
 * ```
 */
 class PostOrderTreeIterator<T,E: TreeElement<T, E>>(root: TreeElement<T, E>) : Iterator<TreeElement<T, E>> {

    private val stack = ArrayDeque<TreeElement<T, E>>()

    init {
        stack.addAll(getChildrenStack(root))
    }

    override fun hasNext(): Boolean = stack.isNotEmpty()

    override fun next(): TreeElement<T, E> {
        return stack.removeFirst()
    }

    private fun getChildrenStack(node: TreeElement<T, E>): ArrayDeque<TreeElement<T, E>> {
        val stack = ArrayDeque<TreeElement<T, E>>()
        if (node.isLeaf) {
            return ArrayDeque(listOf(node))
        }
        if(node is NodeElement)
           node.children?.forEach { stack.addAll(getChildrenStack(it)) }
        stack.addLast(node)
        return stack
    }
}
